package org.example.myleet.rosalind.sptd;

import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    /**
     * https://rosalind.info/problems/sptd/
     * [Rosalind]【DFS+集合比较】Phylogeny Comparison with Split Distance
     * 本题关键是先找出两棵树的所有split集合，然后比较两个split集合中share了哪些split，即s(T1,T2)
     * dsplit(T1,T2)=2(n−3)−2s(T1,T2)
     */
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line = br.readLine();
        String[] taxa = line.split(" ");
        NewickTreeNode tree1 = NewickTreeUtil.parse(null, br.readLine());
        NewickTreeNode tree2 = NewickTreeUtil.parse(null, br.readLine());
        List<Set<String>> tree1Splits = getAllSplits(tree1, taxa.length);
        List<Set<String>> tree2Splits = getAllSplits(tree2, taxa.length);
        int shareCnt = 0;
        for (int i = 0; i < tree1Splits.size(); ++i) {
            Set<String> split1 = tree1Splits.get(i);
            for (int j = 0; j < tree2Splits.size(); ++j) {
                Set<String> split2 = tree2Splits.get(j);
                if (split1.size() == split2.size() && split1.containsAll(split2)) {
                    ++shareCnt;
                }
            }
        }
        System.out.println(2 * (taxa.length - 3) - 2 * shareCnt);
    }
    private static List<Set<String>> getAllSplits(NewickTreeNode root, int taxaSize) {
        List<Set<String>> splits = new ArrayList<>(taxaSize);
        dfs(root, taxaSize, splits);
        return splits;
    }
    private static Set<String> dfs(NewickTreeNode node, int taxaSize, List<Set<String>> splits) {
        Set<String> result = new HashSet<>();
        if (node.getValue().length() > 0) {
            result.add(node.getValue());
            return result;
        }
        for (NewickTreeNode child : node.getChildren()) {
            result.addAll(dfs(child, taxaSize, splits));
        }
        if (result.size() > 1 && result.size() <= taxaSize - 2) {
            splits.add(result);
        }
        return result;
    }
}
